import java.util.LinkedList;
import java.util.Stack;


public class Parser {
    private static LinkedList<Token> tokenList;
    private static Stack<TreeNode> parseStack;

    
    
    public  Parser()
    {
        tokenList = new LinkedList<Token>();
        parseStack = new Stack<TreeNode>();
        
    }
    
    public void setRoot(LinkedList<Token> list) {
        tokenList = list;
        Grammar.setList(tokenList);
    }
    
    public TreeNode parse(){
        Grammar.nt = tokenList.peek().value;
        Grammar.E();
        if(!(((Token)tokenList.peek()).type == TokenType.Rpal_EndOfFile)) {
            System.out.print("Warning: Words remained");
        }
        
        return parseStack.peek();
    }
    
    private static class  Grammar {
        private static LinkedList<Token> tokenList;
        private static String nt;
        public static void setList(LinkedList<Token> list) {
            tokenList = list;
        }
        
        
        
        
    /*  # Expressions ############################################
        E   -> ?let? D ?in? E       => ?let?
            -> ?fn? Vb+ ?.? E       => ?lambda?
            -> Ew;
        Ew  -> T ?where? Dr         => ?where?
            -> T;
        ##########################################################        */
        static void E() {
            int n = 1;
            if((nt = tokenList.peek().value).equals("let"))
            //E -> ?let? D ?in? E
            {
                tokenList.pop();
                D();
                if((nt = tokenList.peek().value).equals("in")) {
                    tokenList.pop();
                    E();
                    buildTree("let");
                }else {
                    parseErr("in");
                }
            }
            else if((nt = tokenList.peek().value).equals("fn")) 
            //E -> ?fn? Vb+ ?.? 
            {
                tokenList.pop();
                Vb();
                while (!(nt = tokenList.peek().value).equals(".")) {
                    n++;
                    Vb();
                }
                tokenList.pop();
                E();
                if (n == 1) {
                    buildTree("lambda");
                    
                } else {
                    buildTree("lambda", n + 1);
                }
            }
            else
            //E -> Ew
            {
                Ew();
            }
        }
        
        static void Ew() {
            T();
            if((nt = tokenList.peek().value).equals("where")) {
                tokenList.pop();
                Dr();
                buildTree("where");
            }
        }
        
        
        /*
        # Tuple Expressions ######################################
        T   -> Ta ( ?,? Ta )+       => ?tau?
            -> Ta ;
        Ta  -> Ta ?aug? Tc          => ?aug?
            -> Tc ;
        Tc  -> B ?->? Tc ?|? Tc       => ?->?
            -> B ;
        ##########################################################*/
        static void T() {
            int n = 1;
            Ta();
            if((nt = tokenList.peek().value).equals(",")) {
                while((nt = tokenList.peek().value).equals(",")){
                    tokenList.pop();
                    Ta();
                    n++;
                }
                buildTree("tau", n);
            }
            
        }
        
        static void Ta() {
            Tc();
            while((nt = tokenList.peek().value).equals("aug")) {
                tokenList.pop();
                Tc();
                buildTree("aug");
            }
        }
        
        static void Tc() {
            B();
            if((nt = tokenList.peek().value).equals("->")) {
                tokenList.pop();
                Tc();
                if ((nt = tokenList.peek().value).equals("|")) {
                    tokenList.pop();
                    Tc();
                    buildTree("->", 3);
                } else {
                    parseErr("|");
                }
            }
        }
        
        
        /*# Boolean Expressions ####################################
        B   -> B ?or? Bt            => ?or?
            -> Bt ;
        Bt  -> Bt ?&? Bs            => ?&?
            -> Bs ;
        Bs  -> ?not? Bp             => ?not?
            -> Bp ;
        Bp  -> A (?gr? | ?>? ) A    => ?gr?
            -> A (?ge? | ?>=?) A    => ?ge?
            -> A (?ls? | ?<? ) A    => ?ls?
            -> A (?le? | ?<=?) A    => ?le?
            -> A ?eq? A             => ?eq?
            -> A ?ne? A             => ?ne?
            -> A ;
        ##########################################################*/
        static void B() {
            Bt();
            while((nt = tokenList.peek().value).equals("or")) {
                tokenList.pop();
                Bt();
                buildTree("or");
            }
        }
        
        static void Bt() {
            Bs();
            while((nt = tokenList.peek().value).equals("&")) {
                tokenList.pop();
                Bs();
                buildTree("&");
            }
        }

        static void Bs() {
            if ((nt = tokenList.peek().value).equals("not")) {
                tokenList.pop();
                Bp();
                buildTree("not");
            }
            Bp();
        }

        static void Bp() {
            A();
            if ((nt = tokenList.peek().value).equals("gr")
                    || (nt = tokenList.peek().value).equals(">")) {
                tokenList.pop();
                A();
                buildTree("gr");
            } else if ((nt = tokenList.peek().value).equals("ge")
                    || (nt = tokenList.peek().value).equals(">=")) {
                tokenList.pop();
                A();
                buildTree("ge");
            } else if ((nt = tokenList.peek().value).equals("ls")
                    || (nt = tokenList.peek().value).equals("<")) {
                tokenList.pop();
                A();
                buildTree("ls");
            } else if ((nt = tokenList.peek().value).equals("le")
                    || (nt = tokenList.peek().value).equals("<=")) {
                tokenList.pop();
                A();
                buildTree("le");
                
            } else if ((nt = tokenList.peek().value).equals("eq")) {
                tokenList.pop();
                A();
                buildTree("eq");
            } else if ((nt = tokenList.peek().value).equals("ne")) {
                tokenList.pop();
                A();
                buildTree("ne");
            }
        }
        
        /*# Arithmetic Expressions #################################
        A   -> A ?+? At                 => ?+?
            -> A ?-? At                 => ?-?
            -> ?+? At
            -> ?-? At                   => ?neg?
            -> At ;
        At  -> At ?*? Af                => ?*?
            -> At ?/? Af                => ?/?
            -> Af ;
        Af  -> Ap ?**? Af               => ?**?
            -> Ap ;
        Ap  -> Ap ?@? ?<IDENTIFIER>? R  => ?@?
            -> R ;
        ##########################################################*/
        static void A() {
            if((nt = tokenList.peek().value).equals("+")) {
                tokenList.pop();
                At();
            }else if((nt = tokenList.peek().value).equals("-")) {
                tokenList.pop();
                At();
                buildTree("neg");
            }else {
              At();  
            }
            while((nt = tokenList.peek().value).equals("+") || (nt = tokenList.peek().value).equals("-")) {
                String temp = nt;
                tokenList.pop();
                At();
                buildTree(temp);
            }
        }
        
        static void At() {
            Af();
            while((nt = tokenList.peek().value).equals("*") || (nt = tokenList.peek().value).equals("/")) {
                String s = nt;
                tokenList.pop();
                Af();
                buildTree(s);
            }
        }
        
        static void Af() {
            int n = 0;
            Ap();
            while((nt = tokenList.peek().value).equals("**")) {
                tokenList.pop();
                Af();
                n++;
            }
            while(--n > 0) buildTree("**");
        }
        
        static void Ap() {
            R();
            while((nt = tokenList.peek().value).equals("@")) {
                tokenList.pop();
                if(tokenList.peek().type == TokenType.Rpal_Identirfier) {
                    terminal(tokenList.peek());
                    tokenList.pop();//<identifier>???
                    R();
                    buildTree("@", 3);
                }else {
                    parseErr("@");
                }
            }
            
        }
        
        /*# Rators And Rands #######################################
        R   -> R Rn                     => ?gamma?
            -> Rn ;
        Rn  -> ?<IDENTIFIER>?
            -> ?<INTEGER>?
            -> ?<STRING>?
            -> ?true?                   => ?true?
            -> ?false?                  => ?false?
            -> ?nil?                    => ?nil?
            -> ?(? E ?)?
            -> ?dummy?                  => ?dummy? ;
        ##########################################################*/
        static void R() {
            if(Rn()) {
               while(Rn()) {
                 //gamma
                   buildTree("gamma");
               } 
            }
            
        }
        
        static boolean Rn() {
            if ((nt = tokenList.peek().value).equals("true")) {
                terminal(tokenList.peek());
                tokenList.pop();
                return true;
            } else if ((nt = tokenList.peek().value).equals("false")) {
                terminal(tokenList.peek());
                tokenList.pop();
                return true;
            } else if ((nt = tokenList.peek().value).equals("nil")) {
                terminal(tokenList.peek());
                tokenList.pop();
                return true;
            } else if ((nt = tokenList.peek().value).equals("dummy")) {
                terminal(tokenList.peek());
                tokenList.pop();
                return true;
            } else if (tokenList.peek().type == TokenType.Rpal_Integer) {
                terminal(tokenList.peek());
                tokenList.pop();
                return true;
            } else if (tokenList.peek().type == TokenType.Rpal_String) {
                terminal(tokenList.peek());
                tokenList.pop();
                return true;
            } else if (tokenList.peek().type == TokenType.Rpal_Identirfier ) {
                terminal(tokenList.peek());
                tokenList.pop();
                return true;
            } else if ((nt = tokenList.peek().value).equals("(")) {
                tokenList.pop();
                E();
                if ((nt = tokenList.peek().value).equals(")")) {
                    tokenList.pop();
                    return true;
                } else {
                    parseErr(")");
                    return false;
                }
            } else {
                return false;
            }
        }
        
        
        /*# Definitions ############################################
        D   -> Da ?within? D                => ?within?
            -> Da ;
        Da  -> Dr ( ?and? Dr )+             => ?and?
            -> Dr ;
        Dr  -> ?rec? Db                     => ?rec?
            -> Db ;
        Db  -> Vl ?=? E                     => ?=?
            -> ?<IDENTIFIER>? Vb+ ?=? E       => ?fcn_form?
            -> ?(? D ?)? ;
        ##########################################################*/
        static void D() {
            Da();
            if((nt = tokenList.peek().value).equals("within")) {
                tokenList.pop();
                D();
                buildTree("within");
            }
        }
        
        static void Da() {
            int n = 1;
            Dr();
            if((nt = tokenList.peek().value).equals("and")) {
                while((nt = tokenList.peek().value).equals("and")) {
                    n++;
                    tokenList.pop();
                    Dr();
                }
                buildTree("and", n);
            }
            
        }
        
        static void Dr() {
            if((nt = tokenList.peek().value).equals("rec")) {
                tokenList.pop();
                Db();
                buildTree("rec");
            }else {
                Db();
            }
            
        }
        
        static void Db() {
            int n = 0;
            if(Vl()){
                if((nt = tokenList.peek().value).equals("=")) {
                    tokenList.pop();
                    E();
                    buildTree("=");
                    parseStack.peek().setType(NodeType.EQUALS);
                    return;
                }
                while(Vb()) {
                    n++;
                }
                if((nt = tokenList.peek().value).equals("=")) {
                    tokenList.pop();
                    E();  
                    buildTree("function_form", n+2);
                    return;
                }else {
                    parseErr("=");
                }
            }else if((nt = tokenList.peek().value).equals("(")) {
                tokenList.pop();
                D();
                if((nt = tokenList.peek().value).equals(")")) {
                    tokenList.pop();
                    return;
                }else {
                    parseErr(")");
                }
            }else {
                System.out.print("Nothing remained\r\n");
            }
        }
        
        /*# Variables ##############################################
        Vb  -> ?<IDENTIFIER>?
            -> ?(? Vl ?)?
            -> ?(? ?)?                          => ?()?;
        Vl  -> ?<IDENTIFIER>? list ?,?          => ?,??;
        ##########################################################*/
        
        static boolean Vb() {
            if((nt = tokenList.peek().value).equals("(")) {
                tokenList.pop();
                if(Vl()) {
                    if((nt = tokenList.peek().value).equals(")")) {
                        tokenList.pop();
                        return true;
                    }else {
                        parseErr(")");
                        return false;
                    }
                }else if((nt = tokenList.peek().value).equals(")")) {
                    terminal();
                    tokenList.pop();
                    //()
                    return true;
                }else {
                    parseErr(")");
                    return false;
                }
            }else if(tokenList.peek().type == TokenType.Rpal_Identirfier){
                terminal(tokenList.peek());
                tokenList.pop();
                return true;
            }else {
                return false;
            }
        }
        
        static boolean Vl() {
            int n = 0;
            if(tokenList.peek().type == TokenType.Rpal_Identirfier) {
               terminal(tokenList.peek());
               tokenList.pop();
               while((nt = tokenList.peek().value).equals(",")) {
                   tokenList.pop();
                   if(tokenList.peek().type == TokenType.Rpal_Identirfier) {
                       terminal(tokenList.peek());
                       tokenList.pop();
                       n++;
                   }else {
                       parseErr("Identifier");
                       return false;
                   }
               }
               if(n>0) {
                   buildTree(",", n+1);
               }
               return true;
            }else {
               return false;
            }
        }
        
        
        
        /*# Variables ##############################################
        Tree related operation
        ##########################################################*/
        static void buildTree(String s) {
            TreeNode newNode = new TreeNode();
            if(isBinaryNode(s)) {
                newNode.setRightChild(parseStack.pop());
            }
            newNode.setLeftChild(parseStack.pop());
            newNode.setExtraChild(null);
            newNode.name = s;
            newNode.location=0;
            parseStack.push(newNode);
        }
        
        static void buildTree(String s, int number) {
            int count = number;
            TreeNode newNode = null, prevNode = null;
            while(count > 0 ) {
                newNode = new TreeNode();
                if(prevNode != null) {
                    prevNode.setRightChild(newNode);
                }
                newNode.setExtraChild(parseStack.pop());
                newNode.setLeftChild(prevNode);
                newNode.name = s;
                newNode.location = 0;
                prevNode = newNode;
                count --;
            }
            newNode.setRightChild(null);
            parseStack.push(newNode);
        }
        
        static boolean isBinaryNode(String type) {
            if(type.equals("neg")) {
                return false;
            }else if(type.equals("rec")) {
                return false;
            }else if(type.equals("not")) {
                return false;
            }else {
                return true;
            }
        }
        
        static void terminal(Token t) {
            TreeNode newNode = new TreeNode();
            newNode.stringValue = t.value;
            newNode.terminal();
            //????????
            newNode.name = t.value;
            if(t.type == TokenType.Rpal_Integer) {
                newNode.intValue = Integer.parseInt(t.value);
                newNode.setType(NodeType.INT);
            }
            if(t.value.equals("true")) {
                newNode.intValue = 1;
                newNode.setType(NodeType.BOOL);
                newNode.name = "<true>";
                newNode.boolValue = true;
            }
            if(t.value.equals("false")) {
                newNode.intValue = 0;
                newNode.setType(NodeType.BOOL);
                newNode.name = "<false>";
                newNode.boolValue = false;
            }if(t.value.equals("nil")) {
                newNode.intValue = 0;
                newNode.setType(NodeType.NIL);
                newNode.name = "<nil>";
            }if(t.value.equals("dummy")) {
                newNode.intValue = 0;
                newNode.setType(NodeType.DUMMY);
                newNode.name = "<dummy>";
            }
            if(t.type == TokenType.Rpal_String) {
                newNode.stringValue = t.value.substring(1, t.value.length() - 1);
                newNode.setType(NodeType.STR);
            }
            if(t.type == TokenType.Rpal_Identirfier) {
                newNode.stringValue = t.value;
                newNode.setType(NodeType.ID);
            }
                
            parseStack.push(newNode);
        }
        
        static void terminal() {
            TreeNode newNode = new TreeNode();
            newNode.terminal();
            newNode.name = "<()>";
            parseStack.push(newNode);
        }
        
        
        static void parseErr(String s) {
            try {
                throw new Exception("Expect " + s + "\r\n");
            } catch (Exception e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
        }
        
        
    }
}
